package com.simon.study.algorithm.tree;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Objects;

/**
 * <p>
 *
 * @author simon
 */
public class AVLTree {

    TNode   root;
    int     size;

    public static TNode leftRotate(TNode spot){
        TNode node = spot.right;
        spot.right = node.left;
        node.left  = spot;
        return node;
    }


    public static TNode rightRotate(TNode spot){
        TNode node = spot.left;
        spot.left  = node.right;
        node.right = spot;
        return node;
    }

    public static TNode leftRightRotate(TNode node){
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }


    public static TNode rightLeftRotate(TNode spot){
        spot.right = rightRotate(spot.right);
        return leftRotate(spot);
    }


    public static int recursiveHeight(TNode node){
        if(node == null){ return 0; }
        return Math.max(recursiveHeight(node.left), recursiveHeight(node.right))+1;
    }



    public static TNode find(TNode node, int data){
        if(node == null){ return null; }

        if(data < node.getData()){
            return find( node.left, data );
        }else if( data > node.getData() ){
            return find( node.right, data );
        }else{
            return node;
        }
    }

    public void add(int data){
        TNode node = find(root, data);
        if(node == null){
            size ++;
            root = insert(root, data);
        }
    }

    public static TNode insert(TNode node, int data){
        if(node == null){ return new TNode(data); }

        if(data < node.getData()){
            node.setLeft( insert(node.left, data) );
        }else if(data > node.getData()){
            node.setRight( insert(node.right, data) );
        }else{
            return node;
        }

        return fix(node);
    }

    private static TNode fix(TNode node){
        // left
        if((height(node.left) - height(node.right)) > 1 ){
            // left left -> rightRotate
            if(height(node.left.left) > height(node.left.right)){
                // left left -> rightRotate
                node = rightRotate(node);
            }else{
                // left right -> left right
                node = leftRightRotate(node);
            }
        }

        // right
        if((height(node.right) - height(node.left)) > 1){
            // right
            if(height(node.right.right) > height(node.right.left)){
                node = leftRotate(node);
            }else{
                // right - left
                node = rightLeftRotate(node);
            }
        }

        return node;
    }


    public static int height(TNode node){
        if(node == null){ return 0; }

        Deque<TNode> stack = new ArrayDeque<>();
        stack.addLast(node);

        int height = 0, child = 0;
        for(TNode top = node; !stack.isEmpty(); top = stack.peekFirst()){
            if(top.left  != null){ stack.addLast(top.left);  child++; }
            if(top.right != null){ stack.addLast(top.right); child++; }

            stack.pop();
            if(child == stack.size()){
                height++; child = 0;
            }
        }
        return height;
    }


    public static TNode findMin(TNode node){
        if(Objects.isNull(node.left)){ return node; }

        return findMin(node.left);
    }


    public static TNode findMax(TNode node){
        if(Objects.isNull(node.right)){ return node; }

        return findMax(node.left);
    }


    public void delete(int data){
        TNode node = find(root, data);
        if(node != null){
            size--;
            root = delete(root, data);
        }
    }

    public static TNode delete(TNode node, int data){
        if(node == null){ return null; }

        else if( data < node.data ){
            node.setLeft(  delete(node.left,  data));
        }
        else if( data > node.data ){
            node.setRight( delete(node.right, data));
        }else{
            if(node.left != null && node.right != null){
                node.data = findMin(node.right).data;
                node.setRight(delete(node.right, node.data));
            }else{
                // left
                if(node.getRight() != null){
                    node = node.getRight();
                }else if(node.getLeft() != null){
                    node = node.getLeft();
                }else{
                    node = null;
                }
            }
        }

        return node != null ? (leaf(node) ? node : fix(node)) : null;
    }

    public static boolean balanced(TNode node){
        return !(Math.abs(height(node.left) - height(node.right)) > 1);
    }

    public static boolean leaf(TNode node){return node.left==null && node.right==null;}


    public void hiarachicalPrint(){
        if(root == null){ return; }

        Deque<TNode> stack = new ArrayDeque<>();
        stack.addLast(root);

        int child = 0;
        for(TNode node = root; !stack.isEmpty(); node = stack.peekFirst()){

            if(node.left  != null){ stack.addLast(node.left);  child++; }
            if(node.right != null){ stack.addLast(node.right); child++; }

            System.out.print( stack.pop() + " ");

            if(child == stack.size()){
                child = 0;
                System.out.println();
            }
        }
    }
}
